package com.tgy.algorithm._经典题目01;

import java.util.PriorityQueue;


class Info {
    int value;
    int row;
    int col;
    public Info(int value, int row,int col) {
        this.value = value;
        this.row = row;
        this.col = col;
    }
}

/**
 * 如果给你一个二维数组，每一个值表示这一块地形的高度求整块地形能装下多少水。
 */
public class _012_二维接水问题 {

    public static int maxWater(int[][] nums) {

        if(nums == null || nums.length == 0 || nums[0].length == 0) {
            return 0;
        }

        PriorityQueue<Info> minHeap = new PriorityQueue<Info>((one, two) -> {
            return one.value - two.value;
        });


        int row = nums.length;
        int col = nums[0].length;
        boolean[][] caches = new boolean[row][col];

        for (int i = 0; i < col; i++) {
            Info info = new Info(nums[0][i], 0, i);
            Info bottomInfo = new Info(nums[row - 1][i],row - 1,i);
            minHeap.add(info);
            minHeap.add(bottomInfo);
            caches[0][i] = true;
            caches[row - 1][i] = true;
        }

        for (int i = 0; i < row; i++) {
            Info info = new Info(nums[i][col - 1], i, col - 1);
            Info leftInfo = new Info(nums[i][0], i, 0);
            minHeap.add(info);
            minHeap.add(leftInfo);
            caches[i][col - 1] = true;
            caches[i][0] = true;
        }

        int maxValue = Integer.MIN_VALUE;
        int water = 0;
        while (!minHeap.isEmpty()) {

            Info poll = minHeap.poll();
            maxValue = Math.max(poll.value,maxValue);

            if (poll.row - 1 >= 0 && !caches[poll.row - 1][poll.col]) {
                int value = maxValue - nums[poll.row - 1][poll.col];
                if (value > 0) {
                    water += value;
                }
                minHeap.add(new Info(nums[poll.row - 1][poll.col],poll.row - 1,poll.col));
                caches[poll.row - 1][poll.col] = true;
            }

            if (poll.row + 1 < row && !caches[poll.row+1][poll.col]) {
                int value = maxValue - nums[poll.row + 1][poll.col];
                if (value > 0) {
                    water += value;
                }
                minHeap.add(new Info(nums[poll.row + 1][poll.col],poll.row + 1,poll.col));
                caches[poll.row + 1][poll.col] = true;
            }

            if (poll.col - 1 >= 0 && !caches[poll.row][poll.col - 1]) {
                int value = maxValue - nums[poll.row][poll.col - 1];
                if (value > 0) {
                    water += value;
                }
                minHeap.add(new Info(nums[poll.row][poll.col - 1],poll.row,poll.col - 1));
                caches[poll.row][poll.col - 1] = true;
            }

            if (poll.col + 1 < col && !caches[poll.row][poll.col + 1]) {
                int value = maxValue - nums[poll.row][poll.col + 1];
                if (value > 0) {
                    water += value;
                }
                minHeap.add(new Info(nums[poll.row][poll.col + 1],poll.row,poll.col - 1));
                caches[poll.row][poll.col + 1] = true;
            }

        }

        return water;
    }

    public static void main(String[] args) {

        int[][] nums = {
                {9,9,9,9,6},
                {9,1,1,1,5},
                {9,9,1,9,9},
                {8,2,3,4,5},
                {9,9,9,9,9}
        };

        int result = maxWater(nums);
        System.out.println(result);
    }
}
